package com.sakura.滑动窗口;

public class Code76_最小覆盖子串 {

    public String minWindow(String s, String t) {

        int[] cnts = new int[128];
        for (char c : t.toCharArray()) {
            cnts[c]--;
        }
        int count = t.length();

        int l = 0, r = 0;
        int n = s.length();
        int len = Integer.MAX_VALUE; // 子串的长度
        int start = 0; // 子串的起始位置
        while (r < n) {
            if (cnts[s.charAt(r)] < 0) {
                count--;
            }
            cnts[s.charAt(r)]++;
            if (count == 0){
                // 账单还清了
                while (cnts[s.charAt(l)] > 0) {
                    cnts[s.charAt(l)]--;
                    l++;
                }
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    start = l;
                }
            }
            r++;
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}
